#include <iostream>
#include <vector>

using namespace std;

/**
 * Move Zeros  283
 * space complexity O(n)
 * time complexity  O(n)
 */
class Solution{
public:
	// 时间复杂度 O(n)  空间复杂度 O(n)
	void moveZeroes(vector<int> & nums){/*{{{*/
		// 先声明新数组，存放所有非零元素
		vector<int> nonZeroElements;

		// 将vec中所有非0元素放入nonZeroElements中
		for(int i = 0;i < nums.size();++i){
			if(nums[i])
				nonZeroElements.push_back(nums[i]);
		}

		// 将nonZeroElements中的所有元素依次放入到nums开始的位置
		for(int i = 0; i < nonZeroElements.size();++i){
			nums[i] = nonZeroElements[i];
		}

		// 将nums剩余的位置放置为0
		for(int i = nonZeroElements.size(); i < nums.size();++i){
			nums[i] = 0;
		}
	}/*}}}*/

	// 时间复杂度 O(n)  空间复杂度 O(1)
	void moveZeroes2(vector<int> & nums){
		// [0,k) 区域全部为非零
		int k = 0;

		// 将非零元素全部前置
		for(int i = 0; i < nums.size(); ++i){
			if(nums[i]){
				nums[k++] = nums[i];
			}
		}

		// 将后面剩余空间全部补0
		for(int j = k; j < nums.size(); ++j)
			nums[j] = 0;

	}

	void moveZeroes3(vector<int> & nums){
		int k = 0;
		// 将非0元素和前面0 交换位置
		for(int i = 0; i < nums.size(); ++i){
			if(nums[i])
				swap(nums[k++], nums[i]);
		}
	}

	//  全是非零元素 不和自己交换位置
	void moveZeroes4(vector<int> & nums){
		int k = 0;
		for(int i = 0; i < nums.size(); ++i){
			if(nums[i])
				if(k != i)
					swap(nums[k++], nums[i]);
				else
					k++;
		}
	}
};

